#include <iostream>
#include <vector>
using namespace std;

void quickSort(vector<int>& a, int l, int r)
{
	if (l >= r) return;
	int i = l - 1, j = r + 1, key = rand() % (r - l + 1) + l, cur = l;
	while (cur < j)
	{
		if (a[cur] < key)
		{
			swap(a[++i], a[cur++]);
		}
		else if (a[cur] > key)
		{
			swap(a[--j], a[cur]);
		}
		else
		{
			++cur;
		}
	}

	quickSort(a, 0, i);
	quickSort(a, j, r);
}

void mergeSort(vector<int>& a, int l, int r)
{
	if (l >= r) return;

	int mid = (l + r) / 2;
	mergeSort(a, l, mid);
	mergeSort(a, mid + 1, r);

	vector<int> tmp;
	int i = l, j = mid + 1;
	while (i <= mid && j <= r)
	{
		if (a[i] < a[j])
		{
			tmp.push_back(a[i]);
			++i;
		}
		else
		{
			tmp.push_back(a[j]);
			++j;
		}
	}
	while (i <= mid)
	{
		tmp.push_back(a[i]);
		++i;
	}
	while (j <= r)
	{
		tmp.push_back(a[j]);
		++j;
	}

	for (int k = l, cur = 0; k <= r; ++k, ++cur)
	{
		a[k] = tmp[cur];
	}
}
int main()
{
	srand(time(nullptr));
	vector<int> a = { 5,5,7,3,9,1,4,6,8,2 };
	quickSort(a, 0, 9);
	for (const auto& e : a)
	{
		cout << e << " ";
	}
	cout << endl;

	vector<int> b = { 5,5,7,3,9,1,4,6,8,2 };
	mergeSort(b, 0, 9);
	for (const auto& e : b)
	{
		cout << e << " ";
	}
	return 0;
}